package demo2;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-09-03
 * Time: 20:07
 */

import java.util.Arrays;

/**
 * 选择排序-直接选择排序思想 : 每一次从待排序的数据中选出最小的元素(或者最大的元素), 存放在起始位置
 * 直到全部元素排序完成
 */
public class SelectSort {

    /**
     * TODO : 时间复杂度分析, 从 i 到 n - 1 所有元素都要和后面进行比较一遍 O(N^2)
     *        空间复杂度分析, 没有开辟额外的空间 O(1)
     *        稳定性分析, 是一种不稳定的排序
     *        效率特别低, 因此在实际中不太常用
     */
    public void selectSort(int[] array) {
        // 最后一个元素 n - 1 个元素比较时已经有序了, 无需在排序
        for (int i = 0; i < array.length - 1; i++) {
            // 从左往右以 i 位置的值挨个为最小向后判断
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[minIndex] > array[j]) {
                    // 将最小元素的下标更新为当前较小的这个值的下标
                    minIndex = j;
                }
            }

            // 将找到的 minIndex 最小的值下标对应元素和 i 位置下标对应元素交换
            // 防止 i 位置本身就是自己, 则不用交换
            if (minIndex != i) {

                swap(minIndex, i, array);
            }
        }
    }

    private void swap(int minIndex, int i, int[] array) {
        int tmp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        SelectSort sort = new SelectSort();
        sort.selectSort(array);
        System.out.println(Arrays.toString(array));
    }
}
